#coding:utf-8
#找到字符串中最长的回文
#最长回文子串
#在线算法
#此解法基于这样的一个事实，每次增加一个字符，可能使结果加1或者二
class Solution:
    def longestPalindrome(self,s):

        if len(s)==0:
            return 0
        maxLen = 1
        start = 0
        for i in range(len(s)):
            if i - maxLen > 0 and s[i-maxLen-1 : i+1]==s[i-maxLen-1 : i+1][::-1]:
                start = i-maxLen-1
                maxLen += 2
                continue
            if i-maxLen >=0 and s[i-maxLen:i+1]==s[i-maxLen:i+1][::-1]:
                start=i-maxLen
                maxLen+=1
        return s[start:start+maxLen]






s = Solution()
t1 = "abcba"
print s.longestPalindrome(t1)
t2 = "cdcdedc"
print s.longestPalindrome(t2)
